package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/8/27 8:49
 */
public class LC72编辑距离 {

    public static int minDistance(String word1, String word2) {
        return dynamicProgramming(word1, word2);
    }

    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        System.out.println(minDistance(word1, word2));
    }

    /**
     * dp[i][j]代表word1[0, i-1]和word2[0, j-1]最近编辑距离
     * 状态转移方程式：当word1[i-1]==word2[j-1]时，不需要进行操作 dp[i][j]=dp[i-1][j-1]。
     * 当word1[i-1]!=word2[j-1]时
     * 操作1：word1增加一个元素，使得word1[i-1]==word2[j-1]，那么就是以下标i-2为结尾的word1与下标为j-1为结尾的word2的最近编辑距离加上
     * 一个新增元素的操作，dp[i][j]=dp[i-1][j]+1。
     * 操作2：word2新增一个元素，使得word1[i-1]==word2[j-1]，那么就是以下标j-2位结尾的word2与下标为i-1位结尾的word1的最近遍历距离加上
     * 一个新增元素的操作，dp[i][j]=dp[i][j-1]+1.
     * 而word2添加一个元素，相当于word1删除一个元素，如 word1="ad"，word2="a"，word2添加一个元素d，也就相当于word1删除一个元素d使得两者相同
     * 操作3：替换元素，word1替换word1[i-1]，使其与word2[j-1]相同，此时不用增加元素，那么以下标i-2为结尾的word1和j-2结尾的word2的最近
     * 编辑距离加上一个替换元素的操作，dp[i][j]=dp[i-1][j-1]+1
     * 相关题目：300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组、1143.最长公共子序列、1035.不相交的线、53.最大子序和、392.判断子序列、
     * 115.不同的子序列、583.两个字符串的删除操作
     */
    private static int dynamicProgramming(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        //dp[i][j]代表word1[0, i-1]和word2[0, j-1]最近编辑距离
        int[][] dp = new int[m + 1][n + 1];
        //初始化，和空串之间的比较
        for (int i = 1; i <= m; i++) dp[i][0] = i;
        for (int j = 1; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
